package sort

import java.util.*

/**
 * 快速排序
 *
 *
 *
 *
 */
val array = arrayOf(72, 6, 57, 88, 60, 42, 83, 73, 48, 85)


fun main(args: Array<String>) {
    quickSortNonRecursiveEntry(array)
    quickSort(array, 0, array.size - 1)
    println("quick sort recursive : " + array.toList())

}

/*递归的快速排序*/
fun quickSort(array: Array<Int>, low: Int, high: Int) {
    if (low < high) {
        val pivotIndex = _quickSort(array, low, high)
        quickSort(array, low, pivotIndex - 1)
        quickSort(array, pivotIndex + 1, high)
    }
}

fun _quickSort(array: Array<Int>, l: Int, h: Int): Int {
    var pivot = array[l]
    var low = l
    var high = h
    while (low < high) {//直到前后两个指针相遇
        while (low < high && array[high] >= pivot)//从后往前找,直到和low相遇
            --high

        array[low] = array[high]

        while (low < high && array[low] <= pivot)
            ++low

        array[high] = array[low]
    }
    array[low] = pivot
    return low
}

/*非递归快速排序*/
fun quickSortNonRecursiveEntry(a: Array<Int>) {
    val array = Array(a.size, { i -> a[i] })
    val stack = Stack<Int>()
    val low = 0
    val high = array.size - 1
    stack.push(low)
    stack.push(high)
    var count = 0
    while (stack.size > 0) {
        val h = stack.pop()
        val l = stack.pop()
        val p = _quickSort(array, l, h)
        //left
        if (l < p - 1) {
            stack.push(l)
            stack.push(p - 1)
        }

        if (p + 1 < h) { //right
            stack.push(p + 1)
            stack.push(h)
        }
        count++

    }
    println("quick sort non-recursive: " + array.toList())
}
